package main.sort;

public class MergeSort extends BaseSort {
    public MergeSort(int[] array) {
        super(array);
        this.name = "归并排序";
    }

    @Override
    public void sort() {
        merge(array, 0, array.length - 1, new int[array.length]);
    }

    /**
     * 有序合并从start到end的两个数组
     *
     * @param array 要处理的数组
     * @param l     要处理的起始位置
     * @param r     结束位置
     * @param temp  临时数组
     *              <br>
     *              [7, 8, 6, 5, 4, 3, 2, 1]  <br>
     *              [7, 8, 5, 6, 4, 3, 2, 1]  <br>
     *              [5, 6, 7, 8, 4, 3, 2, 1]  <br>
     *              [5, 6, 7, 8, 3, 4, 2, 1]  <br>
     *              [5, 6, 7, 8, 3, 4, 1, 2]  <br>
     *              [5, 6, 7, 8, 1, 2, 3, 4]  <br>
     *              [1, 2, 3, 4, 5, 6, 7, 8]
     */
    public void merge(int[] array, int l, int r, int[] temp) {
        if (l >= r) {
            return;
        }
        int mid = (l + r) / 2;
        merge(array, l, mid, temp);
        merge(array, mid + 1, r, temp);

        int i = l, j = mid + 1, t = 0;
        while (i <= mid && j <= r) {
            temp[t++] = array[i] < array[j] ? array[i++] : array[j++];
        }
        while (i <= mid) {
            temp[t++] = array[i++];
        }
        while (j <= r) {
            temp[t++] = array[j++];
        }
        t = 0;
        while (l <= r) {
            array[l++] = temp[t++];
        }
        print();
    }
}
